题目传送门:http://codeforces.com/contest/716/problem/D
官方题解:http://codeforces.com/blog/entry/47169
这题很好玩,有两种写法。
1)暴力最短路,复杂度O(nmlogn)
做法就是每一次找最短路,然后改一改
2)神奇二分,复杂度O(mlognlogm)
将可更改的边拉出来,排成一溜
二分一个点k,使1~k的边为1,其余边为INF
终止条件:k时最短路<=l,k-1时最短路>L
于是第k条边就是关键边,只用考虑这条边的长度即可
感觉好神!
考试的时候,我写的是第一种
#include<bits/stdc++.h> #define LL long long using namespace std; const LL N = 1000+9; const LL M = 20000+9; const LL INF = 1e14; LL head[N],to[M],nxt[M],cost[M],U[M],V[M],dis[N],n,m,L,S,T,sign[M],ty,inq[N],sur[N]; queue<LL> que; inline LL read(){ char c=getchar(); LL ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline void Add_Edge(LL u, LL v, LL d) { static LL TT = 1; to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; cost[TT] = d; to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; cost[TT] = d; } inline LL SPFA(){ for (int i=1;i<=n;i++) dis[i] = INF; dis[S] = 0; que.push(S), inq[S] = 1; while (!que.empty()) { LL w = que.front(); que.pop(); inq[w] = 0; for (LL i=head[w];i;i=nxt[i]) if (~cost[i] && dis[to[i]] > dis[w]+cost[i]) { dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i; if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1; } } return dis[T]; } int main(){ n = read(); m = read(); L = read(); S = read() + 1; T = read() + 1; for (LL i=1,tmp;i<=m;i++) { U[i] = read()+1, V[i] = read()+1; tmp = read(); if (!tmp) tmp = -1, sign[i] = 1; Add_Edge(U[i],V[i],tmp); } if (SPFA() < L) cout<<"NO", exit(0); for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = 1; if ((ty=SPFA()) > L) cout<<"NO", exit(0); for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = INF; LL w = T,len_tmp; while (w != S) {if(sign[sur[w]/2]) cost[sur[w]] = cost[sur[w]^1] = 1; w = to[sur[w]^1];} while ((len_tmp=SPFA()) < L) for (w=T;w!=S;w=to[sur[w]^1]) if (sign[sur[w]/2]) { cost[sur[w]] += L - len_tmp, cost[sur[w]^1] += L - len_tmp; break;} cout<<"YES"<<endl; for (LL i=1;i<=m;i++) if (sign[i] && cost[i*2] == -1) printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,L+1); else printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,cost[i*2]); return 0; }
Hello there! This is kind of off topic but I need some advice from an established blog.
Is it tough to set up your own blog? I’m not
very techincal but I can figure things out pretty quick.
I’m thinking about setting up my own but
I’m not sure where to begin. Do you have any ideas or suggestions?
Cheers
whoah this weblog is excellent i really like studying your
articles. Keep up the great work! You know, lots of individuals are hunting round for this information, you could aid them greatly.
Hi there friends, how is everything, and what you wish for to say concerning this article, in my view its actually remarkable in support of me.
Yes! Finally something about gamefly free trial.
Howdy, i read your blog from time to time and i own a similar one
and i was just wondering if you get a lot of spam responses?
If so how do you prevent it, any plugin or anything you
can recommend? I get so much lately it’s driving me insane so any assistance
is very much appreciated.
Hey there, I think your website might be having browser compatibility issues.
When I look at your website in Firefox, it looks fine
but when opening in Internet Explorer, it
has some overlapping. I just wanted to give you a quick heads up!
Other then that, wonderful blog!
We’re a group of volunteers and starting a brand new scheme in our community.
Your web site offered us with valuable info to work on. You’ve performed
an impressive job and our whole group can be grateful to you.
Good article. I am facing a few of these issues as well..
My family every time say that I am wasting my time here at net,
except I know I am getting experience all the time by reading such pleasant
content.
Attractive section of content. I just stumbled upon your
blog and in accession capital to assert that I get in fact
enjoyed account your blog posts. Any way I will be subscribing to your augment
and even I achievement you access consistently fast.
It is the best time to make some plans for the future and it’s time to be
happy. I have read this post and if I could I want to suggest
you some interesting things or advice. Maybe you could write next articles referring to this
article. I desire to read even more things about it!
Hi there very cool website!! Man .. Beautiful ..
Amazing .. I’ll bookmark your site and take the feeds also?
I am happy to find numerous helpful info
right here within the publish, we want develop extra
strategies in this regard, thank you for sharing.
. . . . .
Hi, i read your blog from time to time and i own a similar one and i was just curious if
you get a lot of spam feedback? If so how do
you stop it, any plugin or anything you can recommend?
I get so much lately it’s driving me mad so any support is very much appreciated.
Thanks for finally writing about >【Codeforces 715B】Complete The Graph
– Qizy’s Database <Loved it!
What’s up, its fastidious piece of writing on the topic of media print, we all be
familiar with media is a fantastic source of data.
I would like to thank you for the efforts you have
put in penning this website. I am hoping to view the same high-grade
content from you later on as well. In fact, your creative writing abilities has
encouraged me to get my own site now 😉
Hello there, just became alert to your blog through Google, and found that it is really informative.
I am going to watch out for brussels. I’ll appreciate if
you continue this in future. Numerous people will be benefited from your writing.
Cheers!
Wow, this article is fastidious, my younger sister is analyzing such things, thus I am going
to inform her.
Simply wish to say your article is as astonishing. The clarity on your
put up is just nice and that i can suppose you are
a professional on this subject. Fine along with your permission let me to snatch your RSS feed to stay updated with forthcoming post.
Thank you a million and please keep up the gratifying work.
Thanks for sharing your thoughts. I truly appreciate your efforts
and I will be waiting for your further post thank
you once again.
Hi! Do you know if they make any plugins to help with SEO?
I’m trying to get my blog to rank for some targeted keywords
but I’m not seeing very good success. If you know of any please share.
Kudos! natalielise pof
A fascinating discussion is worth comment. I believe that you
should publish more about this topic, it may not be a taboo subject but usually people don’t speak about such issues.
To the next! Many thanks!!
wonderful publish, very informative. I’m wondering why the
other specialists of this sector don’t realize this.
You should continue your writing. I’m sure, you have a great readers’ base already!
Quality articles or reviews is the main to be a focus
for the users to pay a quick visit the site, that’s what this web page is providing.
You actually make it seem so easy with your presentation but I find this
matter to be really something which I think I would never understand.
It seems too complex and extremely broad for me.
I am looking forward for your next post, I will
try to get the hang of it!
Hi there! Quick question that’s totally off topic.
Do you know how to make your site mobile friendly? My site looks weird when browsing from my iphone.
I’m trying to find a template or plugin that might
be able to resolve this problem. If you have any suggestions, please share.
Cheers!
Hey I know this is off topic but I was wondering if you knew
of any widgets I could add to my blog that automatically tweet my newest twitter updates.
I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would
have some experience with something like this.
Please let me know if you run into anything. I truly enjoy reading your blog and I look
forward to your new updates.
I am truly pleased to read this weblog posts which contains tons of valuable
facts, thanks for providing such information. plenty of fish natalielise
I was more than happy to find this great site.
I need to to thank you for ones time for this particularly wonderful read!!
I definitely liked every part of it and I have you book-marked to see new things on your
web site.
Today, I went to the beach front with my children. I
found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to
her ear and screamed. There was a hermit crab inside
and it pinched her ear. She never wants to go back!
LoL I know this is totally off topic but I had to tell someone!
Hi mates, its fantastic piece of writing about tutoringand entirely defined, keep it up all the time.
Wonderful goods from you, man. I have understand your stuff
previous to and you are just too great. I actually like what you’ve acquired
here, certainly like what you are stating and the way in which you say it.
You make it enjoyable and you still take care of to keep it sensible.
I cant wait to read far more from you. This is actually a tremendous site.
Hello there! I could have sworn I’ve visited this
blog before but after looking at many of the posts I realized it’s new to me.
Nonetheless, I’m certainly happy I stumbled upon it and
I’ll be book-marking it and checking back frequently!
naturally like your web-site however you need
to test the spelling on quite a few of your posts.
Several of them are rife with spelling problems and I in finding it
very troublesome to tell the truth however I will definitely come again again.
I’m now not certain the place you are getting your info, however
great topic. I must spend a while learning more or figuring
out more. Thanks for fantastic info I was on the lookout for this information for my mission.
I was recommended this website by my cousin. I’m not sure
whether this post is written by him as no one else know such detailed about my problem.
You’re incredible! Thanks!
My coder is trying to persuade me to move to .net from PHP.
I have always disliked the idea because of the expenses.
But he’s tryiong none the less. I’ve been using WordPress on a variety of websites
for about a year and am worried about switching to another platform.
I have heard fantastic things about blogengine.net.
Is there a way I can import all my wordpress posts into it?
Any kind of help would be really appreciated!
This piece of writing is actually a good one it assists new internet people, who are wishing for blogging.
It’s remarkable to go to see this web site and
reading the views of all friends on the topic of this piece
of writing, while I am also keen of getting familiarity.
Today, I went to the beachfront with my children. I found a sea shell and gave it to my 4 year
old daughter and said “You can hear the ocean if you put this to your ear.” She
placed the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear.
She never wants to go back! LoL I know this is totally off topic but I had to tell someone!
What a information of un-ambiguity and preserveness of precious familiarity on the topic of unpredicted
feelings.
I am regular visitor, how are you everybody? This article posted at this web page is truly pleasant.
Hello, i believe that i saw you visited my weblog so i got here to go back the desire?.I’m trying to find issues to
enhance my site!I guess its ok to make use of some of your concepts!!
It’s genuinely very difficult in this active
life to listen news on Television, so I simply use web for that purpose, and get the newest information.
Hi there! I just wanted to ask if you ever
have any trouble with hackers? My last blog (wordpress) was hacked and I ended up losing several weeks of
hard work due to no data backup. Do you have any solutions to protect
against hackers?
An outstanding share! I have just forwarded this onto a coworker who
had been conducting a little research on this.
And he in fact bought me breakfast due to the fact that I discovered it for him…
lol. So allow me to reword this…. Thank YOU for the meal!!
But yeah, thanx for spending time to discuss this matter here on your web site.
Hi there! I’m at work browsing your blog from my new iphone 3gs!
Just wanted to say I love reading through your
blog and look forward to all your posts! Carry on the fantastic work!
Way cool! Some very valid points! I appreciate you writing this article and the rest of the site is very good.
Hello there, You’ve done a fantastic job. I will definitely digg it and personally recommend to my friends.
I am confident they’ll be benefited from this site.
What’s up to all, the contents present at this site are really remarkable for people experience, well,
keep up the nice work fellows.
I couldn’t refrain from commenting. Perfectly written!
I could not resist commenting. Very well written!
No matter if some one searches for his vital thing, therefore he/she needs to be available that in detail, thus that thing is maintained over here.
This is my first time go to see at here and i am truly impressed
to read all at single place.
Excellent items from you, man. I’ve take into account your stuff prior to
and you’re just too magnificent. I really like what you’ve got right here,
certainly like what you’re saying and the best way wherein you assert it.
You make it entertaining and you continue to care for to stay it wise.
I cant wait to learn much more from you. This is actually a
wonderful site.
Hmm is anyone else having problems with the images on this blog loading?
I’m trying to determine if its a problem on my end or if
it’s the blog. Any responses would be greatly appreciated.
Today, while I was at work, my cousin stole my iphone and tested
to see if it can survive a 40 foot drop, just so she can be a youtube sensation. My iPad is now broken and she has 83 views.
I know this is completely off topic but I had to share it with someone!
Hello to every , since I am genuinely keen of reading this
webpage’s post to be updated on a regular basis. It contains
fastidious stuff.
It’s remarkable to pay a quick visit this website
and reading the views of all colleagues on the topic of this
paragraph, while I am also keen of getting experience.
Hey there! I realize this is sort of off-topic however I had to ask.
Does running a well-established blog such as yours
require a large amount of work? I am completely new to running
a blog but I do write in my diary every day. I’d like to start a blog so I can easily share my
personal experience and thoughts online. Please let me know if
you have any ideas or tips for brand new aspiring blog owners.
Appreciate it!
Hey there are using WordPress for your site platform?
I’m new to the blog world but I’m trying to get started and create my own. Do you need any html
coding knowledge to make your own blog? Any help would be really appreciated!
You really make it seem so easy with your presentation but I
find this matter to be actually something which I think
I would never understand. It seems too complicated and extremely
broad for me. I am looking forward for your next post,
I’ll try to get the hang of it!
I’m not that much of a internet reader to be honest but your sites really nice, keep it up!
I’ll go ahead and bookmark your site to come back down the road.
Many thanks
Its such as you read my thoughts! You seem to understand
so much approximately this, like you wrote the ebook in it or something.
I believe that you simply can do with some % to pressure the message house a bit, but other than that, this
is excellent blog. A fantastic read. I’ll certainly be back.
We’re a group of volunteers and opening a new scheme in our community.
Your web site offered us with valuable info to work on. You’ve done a formidable job and our whole community will be grateful to you.
Quality content is the main to attract the people
to pay a visit the web page, that’s what this web site is providing.
Wonderful, what a blog it is! This web site gives useful information to us, keep it
up.
Hello this is somewhat of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually
code with HTML. I’m starting a blog soon but have no coding expertise
so I wanted to get guidance from someone with experience.
Any help would be enormously appreciated!
Hi! Would you mind if I share your blog with my facebook group?
There’s a lot of folks that I think would really enjoy your content.
Please let me know. Cheers
I think the admin of this web site is truly working hard in favor of his
web site, as here every material is quality based data.
Attractive component to content. I simply stumbled upon your blog and in accession capital to say that I
get actually loved account your blog posts.
Any way I will be subscribing to your feeds or even I achievement you access consistently fast.
Thanks a bunch for sharing this with all people you really recognise
what you are speaking about! Bookmarked. Kindly also discuss with my website =).
We may have a hyperlink exchange contract between us
This article will help the internet people for building
up new webpage or even a weblog from start to end.
Hi friends, its fantastic post concerning teachingand fully
explained, keep it up all the time.
Your means of telling the whole thing in this paragraph is
really pleasant, every one be capable of simply be aware of it, Thanks a lot.
Its like you read my mind! You seem to know a lot about this, like you wrote the book in it or something. I think that you can do with a few pics to drive the message home a little bit, but other than that, this is wonderful blog. A great read. I’ll certainly be back.
Excellent web site. Lots of useful info here. I’m sending it to several pals ans additionally sharing in delicious.
And naturally, thank you to your effort!
WOW just what I was looking for. Came here by searching for sling tv
Fantastic website. Plenty of helpful info here. I’m sending it to some friends ans also sharing in delicious.
And certainly, thank you in your effort!
Hello to all, how is all, I think every one is getting more from this web site, and your views are nice in support of new
visitors.
If you want tto obtain much from thhis piece of writing then you
have to apply these techniques to your won blog.
Hi there outstanding website! Does running a blog such as this take
a lot of work? I’ve absolutely no understanding of programming but I had been hoping to start my own blog
soon. Anyhow, should you have any recommendations or techniques for new blog owners
please share. I know this is off topic nevertheless
I just wanted to ask. Appreciate it!
Howdy! Someone inn mmy Facebook group shared this website with us so I came to check
it out. I’m definitely enjoying the information. I’m book-marking and will be tweeting this to my followers!
Exceptiknal blog and wonderful style andd design.
I blog often and I seriously thank you for your content.
Your article has really peaked my interest. I am going to bookmark your blog and
keep checking for new information about once per week.
I opted in for your RSS feed as well.
Wow, superb blog layout! How long have you been blogging for?
you made blogging look easy. The overall look of your site is
wonderful, as well as tthe content!
Hi everybody, here every one is sharing these kinds of familiarity, so it’s nice to read this weblog, and I used to visit this weblog every day.
I must thank you for the efforts you’ve put in penning this website.
I am hoping to see the same high-grade content from
you later on as well. In fact, your creative writing abilities has encouraged me to get my own, personal blog now 😉
Fantastic goods from you, man. I’ve understand your suff previous tto and you’re just extremely wonderful.
I really like what you’ve acquired here, really like wht you are saying and the way iin which you say it.
Youu make it enjoyable and you still take care of to keep itt
wise. I cant wait to reead far more frm you. Thiss is
really a tremendous website.
Oh my goodness! Amazing article dude! Many thanks, However I am hzving troubles
with your RSS. I don’t understand the reason why I am unable too join it.
Is there anybody else getting similar RSS problems?
Anybody who knows the answer will you kindly respond? Thanks!!
Aw, this was an extremely good post. Taking the time
and actual effort to generate a really good article… but what can I say… I procrastinate a lot and don’t seem to get anything
done.
Hey there I am so thrilled I found your web site,
I really found you by mistake, while I was searching on Yahoo for
something else, Regardless I am here now and would just like to say cheers for
a incredible post and a all round enjoyable blog (I also love the theme/design), I don’t
have time to read it all at the minute but I have bookmarked
it and also included your RSS feeds, so when I have time I will be back to read much
more, Please do keep up the awesome b.
Great write-up, I am regular visitor of one?¦s site, maintain up the excellent operate, and It’s going to be a regular visitor for a lengthy time.